package day_2022_9_to_12.Day;

/**
 * @author haomin
 * @date 2022/09/07 18:13
 **/
public class Day5_5_Intervew13_MovingCount {
    class Solution {
        public int movingCount(int m, int n, int k) {
            boolean[][] mat = new boolean[m][n];
            return dfs(0, 0, m, n, k, mat);
        }
        private int dfs(int i, int j, int m, int n, int k, boolean[][] mat){
            if(i >= m || j >= n || mat[i][j] || (i/10 + i%10 + j/10 + j%10) > k)
                return 0;
            return 1 + dfs(i+1, j, m, n, k, mat) + dfs(i, j+1, m, n, k, mat);
        }
    }
}